#include<iostream>
#include<string>
#include<time.h>
#include<list>
#include<vector>
#include<cstring>
#include<cmath>
#include "args.hxx"
#include"Util.h"
#include"Framework.h"
#include"Corepruning.h"
#include"preProcess.h"
#include"MVQBP.h" 

#define FILELEN 1024

int curBest;
MVQBPack debug;

int dep = 0, id = 0;

bool check(vector<int> S, vector<int> C, vector<vector<int> >&E, int bip, int graphSize, double alpha, double beta, int thetaL, int thetaR) {
    int n = E.size();
    vector<bool> isValid(n, 0);
    for (int i = 0; i < S.size(); ++i) {
        isValid[S[i]] = 1;
    }
    for (int i = 0; i < C.size(); ++i) {
        isValid[C[i]] = 1;
    }

    int totL = 0, totR = 0;
    for (int i = 0; i < bip; ++i) totL += isValid[i];
    for (int i = bip; i < graphSize; ++i) totR += isValid[i];
    bool val = 1;

    if (totR < thetaR || totL < thetaL) return 0;

    int limitL = ceil(alpha * totR);
    int limitR = ceil(beta * totL);

    for (int i = 0; i < S.size(); ++i) {
        int u = S[i]; int sum = 0;
        for (int v : E[u]) sum += isValid[v];
        val &= u < bip ? (sum >= limitL) : (sum >= limitR);
    }

    for (int i = 0; i < C.size(); ++i) {
        int u = C[i]; int sum = 0;
        for (int v : E[u]) sum += isValid[v];
        val &= u < bip ? (sum >= limitL) : (sum >= limitR);
    }

    return val;
}

bool check2(vector<int> S, vector<int> C, vector<vector<int> >&E, int bip, int graphSize, int thetaL, int thetaR) {
    int n = E.size();
    vector<bool> isValid(n, 0);
    for (int i = 0; i < S.size(); ++i) {
        isValid[S[i]] = 1;
    }
    for (int i = 0; i < C.size(); ++i) {
        isValid[C[i]] = 1;
    }

    int totL = 0, totR = 0;
    for (int i = 0; i < bip; ++i) totL += isValid[i];
    for (int i = bip; i < graphSize; ++i) totR += isValid[i];
    bool val = 1;

    if (totR < thetaR || totL < thetaL) return 0;
    return 1;
}

int forceAns;
vector<int> force;


void MVQB_FORCE(vector<int> S, vector<int> C, vector<vector<int> >&E, int bip, int graphSize, double alpha, double beta, int thetaL, int thetaR) {
    if (S.size() + C.size() < forceAns) return ;
    if (!check2(S, C, E, bip, graphSize, thetaL, thetaR)) return ;
    if (check(S, C, E, bip, graphSize, alpha, beta, thetaL, thetaR)) {
        forceAns = S.size() + C.size();
        force.clear();
        for (int u : S) force.push_back(u);
        for (int u : C) force.push_back(u);

        return ;
    }
    vector<int> nS = S;
    vector<int> nC = C;
    if (C.empty()) return ; 
    //printf("%d\n", nC.back());
    nS.push_back(nC.back());
    nC.pop_back();
    MVQB_FORCE(nS, nC, E, bip, graphSize, alpha, beta, thetaL, thetaR);
    nS = S;
    nC = C;
    nC.pop_back();
    MVQB_FORCE(nS, nC, E, bip, graphSize, alpha, beta, thetaL, thetaR);
}

void MVQBP_SUB(MVQBPack cur, vector<vector<int> >&E) {
    if (curBest >= cur.validSize()) return ; //Proposition 6
    if (cur.SL.size() + cur.CL.size() < cur.thetaL || cur.SR.size() + cur.CR.size() < cur.thetaR) return ; //too small
    if (cur.JudgeBiclique()) {
        curBest = cur.validSize();
        debug = cur;
        // cur.Debug();
        return ;
    }

    // ++id;
    // printf("%d\n", id);
    

    int UBL, UBR, LBL, LBR, minSL, minSR;
    cur.CalcLimit(UBL, UBR, LBL, LBR, minSL, minSR);
    if (UBL + UBR <= curBest || minSL < (int)ceil(cur.alpha * LBR) || minSR < (int)ceil(cur.beta * LBL)) return; //Proposition 6
    if (UBL < LBL || UBR < LBR) return; //Proposition 5


    cur = cur.Prune7_1(UBL, UBR, E);
    if (cur.SL.size() + cur.CL.size() < cur.thetaL || cur.SR.size() + cur.CR.size() < cur.thetaR) return ; //too small
    cur.CalcLimit(UBL, UBR, LBL, LBR, minSL, minSR);
    if (UBL + UBR <= curBest || minSL < (int)ceil(cur.alpha * LBR) || minSR < (int)ceil(cur.beta * LBL)) return; //Proposition 6
    if (UBL < LBL || UBR < LBR) return; //Proposition 5
    //if (cur.SL.size() + cur.CL.size() < cur.thetaL || cur.SR.size() + cur.CR.size() < cur.thetaR) return ; //too small
    if (cur.JudgeBiclique()) {
        curBest = cur.validSize();
        debug = cur;
        cur.Debug();
        return ;
    }

    cur = cur.Prune7_2(LBL, LBR, E);
    if (cur.SL.size() + cur.CL.size() < cur.thetaL || cur.SR.size() + cur.CR.size() < cur.thetaR) return ; //too small
    cur.CalcLimit(UBL, UBR, LBL, LBR, minSL, minSR);
    if (UBL + UBR <= curBest || minSL < (int)ceil(cur.alpha * LBR) || minSR < (int)ceil(cur.beta * LBL)) return; //Proposition 6
    if (UBL < LBL || UBR < LBR) return; //Proposition 5
    //if (cur.SL.size() + cur.CL.size() < cur.thetaL || cur.SR.size() + cur.CR.size() < cur.thetaR) return ; //too small
    if (cur.JudgeBiclique()) {
        curBest = cur.validSize();
        debug = cur;
        cur.Debug();
        return ;
    }
    int wSR, wSL, wCR, wCL;
    cur.FindPivot(wSL, wSR, wCL, wCR);
    if (id == 74) printf("%d%d%d%d\n", wSL, wSR, wCL, wCR);
    if (wSL == -1 && wSR == -1) {
        if (wCR == -1 || (wCL != -1 && cur.siz[wCL] < cur.siz[wCR])) {
            MVQBPack nex = cur.Branch2Add(wCL, 1, E);
            MVQBP_SUB(nex, E);
            nex = cur.Branch2Del(wCL, 1, E);
            MVQBP_SUB(nex, E);
        } else {
            MVQBPack nex = cur.Branch2Add(wCR, 0, E);
            MVQBP_SUB(nex, E);
            nex = cur.Branch2Del(wCR, 0, E);
            MVQBP_SUB(nex, E);
        }
    } else {
        if (wSR == -1 || (wSL != -1 && cur.siz[wSL] < cur.siz[wSR])) {
            vector<int> vec; int p, q;
            cur.PreBranch1L(vec, p, q, wSL, UBR, E);
            for (int i = 0; i <= q; ++i) {
                MVQBPack nex = cur.Branch1(vec, wSL, p, q, i, 1, E);
                MVQBP_SUB(nex, E);
            }
        } else {
            vector<int> vec; int p, q;
            cur.PreBranch1R(vec, p, q, wSR, UBL, E);
            for (int i = 0; i <= q; ++i) {
                MVQBPack nex = cur.Branch1(vec, wSR, p, q, i, 0, E);
                MVQBP_SUB(nex, E);
            }
        }
    }
}

int main(int argc, char** argv) {

	char filepath[1024] = ".........";

	double alpha = 0.0, beta = 0.0;

    int k=0;  //禁用

	args::ArgumentParser parser(
        "An algorithm for computing the maximum quasi-biclique\n");

    args::HelpFlag help(parser, "help", "Display this help menu",
                        {'h', "help"});
    args::Group required(parser, "", args::Group::Validators::All);

    args::ValueFlag<std::string> benchmark_file(
        parser, "benchmark", "Path to benchmark", {'f', "file"},
        "");

    args::ValueFlag<int> Threshold_l(parser, "Lower Bound", "The lower bound of the size of quasi-biclique", {'u', "u"}, 1);

    args::ValueFlag<int> Threshold_r(parser, "Lower Bound", "The lower bound of the size of quasi-biclique", {'v', "v"}, 1);

	args::ValueFlag<int> Results(parser, "Num of results", "Num of results", {'K', "K"}, 1); 

	args::ValueFlag<bool> IsTwoHopReduce(parser, "para of two hop reduce", "The parameter reduce", {'r', "r"}, 1);  

    args::ValueFlag<double> Alpha(parser, "para alpha", "The parameter alpha", {'a', "alpha"}, 1);
    
    args::ValueFlag<double> Beta(parser, "para beta", "The parameter beta", {'b', "beta"}, 1);

    try {
        parser.ParseCLI(argc, argv);
    } catch (args::Help) {
        std::cout << parser;
        return 0;
    } catch (args::ParseError e) {
        std::cerr << e.what() << std::endl;
        std::cerr << parser;
        return 0;
    } catch (args::ValidationError e) {
        std::cerr << e.what() << std::endl;
        std::cerr << parser;
        return 0;
    }

	strncpy(filepath, args::get(benchmark_file).c_str(), FILELEN);
    ofstream file("./a1.txt", ios::app);
    streambuf *coutbuf = cout.rdbuf(); // 保存 cout 的缓冲区指针
    cout.rdbuf(file.rdbuf()); // 将 cout 的缓冲区指针指向文件流的缓冲区

	alpha = args::get(Alpha);
    beta = args::get(Beta);
    bool isTwoHopReduce = args::get(IsTwoHopReduce);
    int theta_l = args::get(Threshold_l);
    int theta_r = args::get(Threshold_r);
    cout<<"---------------"<<filepath<<" a,b,lb_L,lb_R,r: "<<alpha<<" "<<beta<<" "<<theta_l<<" "<<theta_r<<" "<<isTwoHopReduce<<"--------------"<<endl;
    if(alpha<=0.5 || beta<=0.5){
        cout<<"alpha and beta should be larger than 0.5"<<endl;
        exit(-1);
    }

    int top_k=args::get(Results);  


	Util util;
	int bi=0;
    int *degree=NULL;
    int **Graph=NULL;
    int graph_size=util.ReadGraph(filepath,Graph,degree,bi);
    CoreLocate core(Graph, degree, graph_size,bi,ceil(theta_r*alpha),ceil(theta_l*beta));
    core.Coredecompose();  //计算coreness
    int **pG=NULL;
    int *pd=NULL;
    int pb=0;
    int pgs=core.CorePrune(pG,pd,pb);  
    cout<<"pgs: "<<pgs<<endl;
    //printf("pb : %d\n", pb);

    CorePack corepack(Graph, degree, graph_size,bi,ceil(theta_r*alpha),ceil(theta_l*beta));
    PrePack prepack(theta_l, theta_r);
    CorePack cur = prepack.PreProcess(corepack);

    curBest = 0;
    for (int i = 0; i < cur.bipartite; ++i) {
        MVQBPack st(i, cur.E, alpha, beta, cur.bipartite, cur.graphSize, theta_l, theta_r);
        printf("i: %d\n", i);
        MVQBP_SUB(st, cur.E);
    }
    debug.Debug();
    puts("end");


    // forceAns = 0;
    // for (int i = 0; i < cur.bipartite; ++i) {
    //     vector<int> S; S.clear();
    //     vector<int> C; C.clear();
    //     S.push_back(i);
    //     for (int j = 0; j < cur.graphSize; ++j)
    //         if (i != j) C.push_back(j);
        
    //     MVQB_FORCE(S, C, cur.E, cur.bipartite, cur.graphSize, alpha, beta, theta_l, theta_r);
    // }

    // puts("FORCE:");
    // printf("forceAns: %d\n", forceAns);
    // for (int u : force) printf("%d ", u); puts("");


    //CorePack cur = corepack.FindBiCore(corepack.lowL, corepack.lowR);
    //printf("%d\n", cur.E.size());
    //puts("test");
    //for (int i = 0; i < cur.graphSize; ++i) printf("%d ", cur.trueID[i]);
    //printf("%d %d\n", cur.lowL, cur.lowR);

    
    Framework bkmb(pG,pd,pgs,pb,alpha,beta,theta_l,theta_r,top_k,isTwoHopReduce);
    time_t s1 = clock();
    bkmb.PBIE();
    time_t s2 = clock();
    cout<<"Running Time: "<<((double)(s2-s1)/CLOCKS_PER_SEC)<<" sec"<<endl;
    // cout<<bkmb.MaxBP<<endl;
    while(!bkmb.res_top_k.empty()){
        subgraph g=bkmb.res_top_k.top();
        cout<<g<<endl;
        bkmb.res_top_k.pop();
    }
    cout<<"******END!******"<<endl;

    cout.rdbuf(coutbuf);

    // 关闭文件流
    file.close();
	return 0;
}